1. Field of the Invention
The present invention generally relates to the field of computers and, in particular, to systems and methods for compressing and/or decompressing data corresponding to 3D finite element meshes.
2. Description of the Related Art
A simple representation of a tetrahedral mesh whose boundary is a manifold surface typically consists of two tables: a vertex table (which keeps vertex coordinates and vertex data, such as temperature or pressure, for instance) and a tetrahedron table (which stores quadruples of vertex indices, representing vertex sets for each one of the m tetrahedra in the mesh). The tetrahedron table describes explicitly only the vertex incidence for each tetrahedron. However, all other connectivity information, like tetrahedron-face or triangle-vertex incidence can be derived from it algorithmically. For a mesh with one million vertices and six million tetrahedra, the tetrahedron table requires 128m≈7.68xc3x97108 bits if 4-byte pointers are used to reference vertices or 80m≈4.8xc3x97108 bits if the vertex references are stored as 20-bit integers crossing the byte boundaries. The total size of the vertex coordinates and data (12-bit coordinates and 16-bit for a single scalar value) of such a mesh amounts to 5.2xc3x97107 bits: almost ten times less. Therefore, the connectivity information dominates the storage cost.
Numerous data structures have been proposed that combine adjacency and incidence information complex (see J. Rossignac, Through the cracks of the solid modeling milestone, From Object Modeling to Advanced Visual Communication, Eds. S. Coquillard, W. Strasser, P. Stucki, Springer-Verlag, pp. 1-75, 1994) for a review. Examples include winged-edge representation (see B. G, Baumgart, Winged Edge Polyhedron Representation, AIM-79, Stanford University, Report STAN-CS-320, 1972, and B. G. Baumgart, A Polyhedron Representation for Computer Vision, AFIPS Nat. Conf Proc., Vol. 44, 589-596, 1975), face-adjacency hypergraph (see L. Floriani and B. Falcidieno, A Hierarchical Boundary Model for Solid Object Representation, ACM Transactions on Graphics 7(1), pp. 42-60, 1988), half-edge structure (see M. Mantyla, An Introduction to Solid Modeling, Computer Science Press, Rockville, Md. 1988, and Y. E. Kalay, The Hybrid Edge: A Topological Data Structure for Vertically Integrated Geometric Modeling, Computer-Aided Design 21(3), pp. 130-140, 1989), radial-edge structure (see E. Gursoz and F. Prinz, Boolean Set Operators on Non-Manifold Boundary Representation Objects, Computer Aided Design 23(1), pp. 33-39, January/February 1991, and E. Gursoz, Y. Choi and F. Prinz, Node-Based Representation of Non-Manifold Surface Boundaries in Geometric Modeling, In: J. Turner, M. Wozny and K. Preiss eds., Geometric Modeling for Product Engineering, North-Holland 1989), and selective geometric complex (see J. Rossignac and M. O""Connor, SGC: A Dimension-independent Model for Pointsets with Internal Structures and Incomplete Boundaries, in Geometric Modelingfor Product Engineering, Eds. M. Wosny, J. Turner, K. Preiss, North-Holland, pp. 145-180, 1989).
The goal behind the design of these data structures is to provide an efficient way of accessing different kinds of adjacency information without taking up much storage space. A common idea is to store some of the adjacency relations (possibly in a partial form) explicitly and use them to derive the ones which are not explicitly stored. For example, in the winged-edge representation, each face and vertex point to one of the adjacent edges and each edgexe2x80x94to its endpoints, the two adjacent faces and the four edges adjacent to that edge and the neighboring two faces. Using the above relations it is possible to compute all others (for example, all edges adjacent to a face or all edges adjacent to a vertex) in time proportional to the local complexity of the mesh (for our two examples, the number of edges of the face and the number of edges our of a vertex, respectively). One of the concerns is to reduce storage space needed to keep adjacency information while minimizing access time. Therefore, it is not fair to treat boundary data structures as a compression scheme. In fact, as shown in T. C. Woo, A Combination Analysis of Boundary Data Structure, IEEE Computer Graphics and Applications, Vol. 5, pp. 19-27, 1985, such a data structure requires at least 4E pointers, where E is the number of edges of the meshxe2x80x94more than tetrahedron table.
Staadt and Gross (see O. Staadt and M. Gross, Progressive Tetrahedralization, Proc. IEEE Visualization, pp. 397:402, Research Triangle Park, Oct. 18-23, 1998) and Trotts et al (see I. Trotts, B. Hamann, K. Joy, D. Wiley, Simplification of Tetrahedral Meshes, Proc. IEEE Visualization, pp. 287:295, Research Triangle Park, Oct. 18-23, 1998) independently propose a tetrahedral mesh simplification process, which removes tetrahedra by collapsing their edges in a sequence that attempts to minimize, at each stage, the error computed using different cost functions. Such a simplification may be viewed as a lossy compression technique and complements our loss-less compression, which may be used to compactly encode the simplified meshes.
Deering""s approach (see M. Deering, Geometric Compression, Computer Graphics (Proc. SIGGRAPH), p. 13-20, August 1995) is a compromise between a standard triangle strip and a general scheme for referencing any previously decoded vertex. Deering uses a 16 register cache to store temporarily 16 of the previously decoded vertices for subsequent uses. One could envision extending the notion of a triangle strip to tetrahedra. Keeping 3 registers for the last 3 vertices used, each new tetrahedron will be defined by these 3 vertices and a fourth vertex either new (the next vertex received in the compressed input stream) or previously received (and identified by its location or id in main memory or cache). One of the vertices in the registers will be replaced by the forth one and the operation repeated. Unfortunately, we do not know of simple and efficient algorithms for identifying the suitable sequence of tetrahedra.
Hoppe""s Progressive Meshes (see H. Hoppe, Progressive Meshes, Computer Graphics (Proc. SIGGRAPH), P. 99-108, August 1996) permit to transfer a 3D mesh progressively, starting from a coarse mesh and then inserting new vertices one by one. Instead of a vertex insertion to split a single triangle, as suggested in D. Dobkin and D. Kirkpatrick, A linear algorithm for determining the separation of convex polyhedra, Journal of Algorithms, Vol. 6, pp. 381-392, 1985, for convex polyhedra, Hoppe applies a vertex insertion that is the inverse of the edge collapse operation popular in mesh simplification techniques (see H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle, Mesh Optimization, Computer Graphics (Proc. SIGGRAPH), p. 19-26, August 1993, R. Ronfard and J. Rossignac, Full-range approximation of triangulated polyhedra, Proc. Eurographics""96, Computer Graphics Forum, pp. C-67, vol. 15, no. 3, August 1996, and P. Heckbert and M. Garland, survey of Polygonal Surface Simplification Algorithms in Multiresolution Surface Modeling Course, ACM SIGGRAPH Course Notes, 1997). A vertex insertion identifies a vertex v and two of its incident edges. It cuts the mesh open at these edges and fills the hole with two triangles. The vertex v is thus split into two vertices. Each vertex is transferred only once in the Hoppe""s scheme.
Hoppe suggests that it may be possible to extend this scheme to tetrahedra. Each vertex split would require identifying one vertex of the current (simplified) version of the mesh and a cone of incident triangles. As the new vertex is extruded into an edge, these triangles would be extruded into new tetrahedra. The cost of this approach is the identification of each vertex (log2v per vertex) and the identification of the cone of incident edges, which on average would require 15 bits per vertex. Although simple, this approach would require roughly (3log2|V|+45)/20 bits per tetrahedron.
The Topological Surgery method recently developed by Taubin and Rossignac G. (see Taubin and J. Rossignac, Geometric Compression Through Topological Surgery, ACM Transactions on Graphics, Vol. 17, no. 2, pp. 84-115, April 1998) also builds a vertex spanning tree of T that splits the surface of the mesh into a binary tree to corridors (generalized triangle strips). The two trees are encoded using a run length code, which for highly complex meshes yields an average of less than two bits per triangle. In addition, one bit per triangle is used to indicate whether the next triangle in the corridor is attached to the left or to the right edge of the previous one. For pathological cases, with a non-negligible proportion of multi-child nodes in two trees, the above approach no longer guarantees linear storage cost. The application of this technique for VRML files is discussed in G. Taubin, W. Horn, F. Lazarus and J. Rossignac, Geometry Coding and VRML, Proceedings of the IEEE, pp. 1228-1243, vol. 96, No. 6, June 1998.
Inspired by D. Kirkpatrick, Optimal Search in Planar Subdivision, SIAM Journal of Computing, vol. 12, pp. 28-35, 1983, and improving on M. Naor, Succinct Representation of General Unlabeled Graphs, Discrete Applied Mathematics, vol. 29, pp. 303-307, North Holland, 1990, and J. Snoeyink and M. van Kerveld, Good Orders for Incremental (Re)construction, Proc. ACM Symposium on Computational Geometry, pp. 400-402, Nice, France, June 1997, Denny and Sohler proposed a technique for compressing planar triangulation of sufficiently large size as a permutation of its vertices (see M. Denny and C. Sohler, Encoding a triangulation as a permutation of its point set, Proc. 9th Canadian Conference on Computational Geometry, pp. 39-43, Ontario, Aug. 11-14, 1997). They show that there are less than 28.2|V|+O(log2|V|) valid triangulation may be associated with a different permutation of these vertices. Their approach requires transmitting an auxiliary triangle that contains all the vertices and the vertices themselves in a suitable order computed by the compression algorithm. Although for sufficiently complex models, the cost of storing the mesh incidents is null, the unstructured order in which the vertices are received in the absence of the incidence graph during their decompression makes it difficult to use predictive techniques for vertex data encoding.
Edgebreaker, introduced by Rossignac (see J. Rossignac, Edgebreaker: Compressing the Connectivity of Triangle Meshes, GVU Technical Report GIT-GVU-98-17, Georgia Institute of Technology), allows to compress the connectivity of a triangular mesh using only about 2 bits per triangle. The compression starts with a depth-search traversal of the dual graph of the mesh. The traversal is topological, i.e., after a triangle is discovered, we first visit the triangle adjacent along its right edge whenever it is possible. Whenever a new triangle is discovered, it is classified as one of five possible types according to which of its edges are shared with triangles which remain undiscovered. A variable length encoding technique is then applied to encode the sequence of types of triangles encountered during the traversal using about 2 bits per triangle. That sequence of triangle types turns out to be sufficient to reconstruct the original mesh. In principle, the Edgebreaker could be extended to the 3D case. However, it is not that simple. For example, sometimes extra information would be needed to encode the offset of the fourth vertex when a new tetrahedron without any new vertices is added to the mesh during decompression. Also, the number of ways in which a removal of a tetrahedron can split the mesh into connected components is considerably larger than in the 2D case. (Other compression schemes for planar graphs and triangulations are discussed in K. Keeler and J. Westbrook, Short Encodings of Planar Graphs and Maps, Discrete Applied Mathematics, No. 58, pp. 239-252, 1995, and G. Turan, On the Succinct Representation of Graphs, Discrete Applied Mathematics 8, pp. 289-294, 1984, among others.)
Therefore, there is a need for improved systems and methods which address these and other shortcomings of the prior art.
Briefly stated, the present invention relates to systems and methods for compressing and/or decompressing data corresponding to 3D finite element meshes. In a preferred embodiment of the present invention, a method for encoding data corresponding to connectivity information of a 3D finite element mesh is provided, with the mesh being formed of tetrahedra. The method includes the steps of: providing data corresponding to connectivity information of the 3D finite element mesh, and; reconfiguring the data based upon identification of faces of each of the tetrahedra where other tetrahedra are to be attached.
In accordance with another aspect of the present invention, a preferred method includes the steps of: receiving data corresponding to connectivity information of the 3D finite element mesh, with the connectivity information including an order of vertices of the tetrahedra; selecting a first face of a first tetrahedron of the 3D finite element mesh; systematically traversing the tetrahedra beginning with the first tetrahedron, and, encoding connectivity information of the 3D finite element mesh based upon a re-ordering of the vertices to define an encoded mesh.
In accordance with yet another aspect of the present invention, a computer readable medium having a computer program stored thereon and being executable by a computer to perform method steps for encoding data corresponding to connectivity information of a 3D finite element mesh is provided. In a preferred embodiment, the method steps include receiving data corresponding to connectivity information of the 3D finite element mesh, and reconfiguring the data based upon identification of faces of each of the tetrahedra where other tetrahedra are to be attached.
In accordance with still another aspect of the present invention, a computer readable medium having a computer program stored thereon and being executable by a computer to perform method steps for reconfiguring encoded data corresponding to connectivity information of a 3D finite element mesh is provided, with the connectivity information defining an ordering of vertices corresponding to a traversal order of the tetrahedra performed during an encoding process. In a preferred embodiment, the method steps include receiving the encoded data corresponding to the connectivity information of the 3D finite element mesh, and a reconstructing the 3D finite element mesh based upon the encoded data.